﻿#include <iostream>

typedef char TElemType;
TElemType Nil = '#';
#define MaxTreeSize 6

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;


void InitBiTree(BiTree &BT) {
    BT = NULL;
}

void CreatBiTree(BiTree &BT) {
    TElemType e;
    std::cin >> e;
    if (e == Nil)
        BT = NULL;
    else {
        BT = (BiTNode *) malloc(sizeof(BiTNode));
        if (!BT) exit(-1); // 申请新结点失败
        BT->data = e;
        CreatBiTree(BT->lchild);  // 递归构造左子树
        CreatBiTree(BT->rchild);  // 递归构造右子树
    }
}

void Visit(BiTree BT) {
    printf("%c", BT->data);
}

int TreeDepth(BiTree BT) {
    int Lh, Rh;
    if (!BT)
        return 0;
    Lh = TreeDepth(BT->lchild);
    Rh = TreeDepth(BT->rchild);
    return Lh > Rh ? Lh + 1 : Rh + 1;
}


/*
 * 设一棵二叉树中各结点的值互不相同，其先序遍历序列和中序遍历序列分别存放于两个一维数组A[1...n]和B[1...n]中，试编写算法建立该二叉树的二叉链表。
 * 操作步骤：先序遍历序列的第一个元素一定试根结点，然后这个根结点可以把中序遍历划分成这个根结点的左子树数组和右子树数组。
 *         同样用中序遍历的左子树数组和包含左子树数组中元素的先序顺序不变的先序数组，又可以在包含左子树数组中元素的先序顺序不变的先序数组第一个根结点已知的情况下划分出左子树和右子树。
 *         同理，右子树也可以不断划分。
 *         重复上述过程，直到某个左子树数组或右子树数组只有一个结点，这个结点一定是叶子结点。
 *
 *(此题是王道书写法，但是调用也有问题，数组下标会越界）
 */


BiTree PreInCreate(TElemType A[], TElemType B[], int l1, int h1, int l2, int h2) {
    // l1, h1为先序的第一和最后一个结点下标，l2，h2为中序的第一和最后一个结点下标
    // 初始调用时，l1=l2=1, h1=h2=n
    BiTNode *root = (BiTNode *) malloc(sizeof(BiTNode));
    root->data = A[0];
    int i;
    for (i = l2; B[i] != root->data; i++);
    int llen = i - l1, rlen = h2 - i;
    if (llen)
        root->lchild = PreInCreate(A, B, l1 + 1, l1 + llen, l2, l2 + llen - 1);
    else
        root->lchild = NULL;
    if (rlen)
        root->rchild = PreInCreate(A, B, h1 - rlen + 1, h1, h2 - rlen + 1, h2);
    else
        root->rchild = NULL;
    return root;
}

int main() {
    BiTree BT;
    InitBiTree(BT);
    TElemType PreOrderSeq[6] = {'1', '2', '4', '5', '3', '6'};
    TElemType InOrderSeq[6] = {'4', '2', '5', '1', '6', '3'};

    printf("根据先序序列和中序序列建立该二叉树的二叉链表（'#'表示子树为空）\n");
    BT = PreInCreate(PreOrderSeq, InOrderSeq, 0, 6, 0, 6);

    printf("使用递归算法，树的高度为：");
    printf("%d\n", TreeDepth(BT));



    return 0;
}